// 实现获取 下一个排列 的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。

// 如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。

// 必须 原地 修改，只允许使用额外常数空间。


function nextPermutation(nums) {
    let i = nums.length - 2; // 向左遍历，i从倒数第二开始是为了nums[i+1]要存在
    while (i >= 0 && nums[i] >= nums[i + 1]) { // 寻找第一个小于右邻居的数
        i--;
    }
    if (i >= 0) { // 这个数在数组中存在，从它身后挑一个数，和它换
        let j = nums.length - 1; // 从最后一项，向左遍历
        while (j >= 0 && nums[j] <= nums[i]) { // 寻找第一个大于 nums[i] 的数
            j--;
        }
        [nums[i], nums[j]] = [nums[j], nums[i]]; // 两数交换，实现变大
    }
    // 如果 i = -1，说明是递减排列，如 3 2 1，没有下一排列，直接翻转为最小排列：1 2 3
    let l = i + 1;
    let r = nums.length - 1;
    while (l < r) { // i 右边的数进行翻转，使得变大的幅度小一些,消除因交换而导致的改变。
        [nums[l], nums[r]] = [nums[r], nums[l]];
        l++;
        r--;
    }
}


//未考虑尾项位于之前的情况
// var nextPermutation = function(nums) {
//     let L=nums.length-2;
//     let R=nums.length-1;
//     while(L>=0){
//         if(nums[R]>nums[L]){
//             [nums[R],nums[L]]=[nums[L],nums[R]];
//             return  nums;
//         }
//         else{
//             L--;
//             R--;
//         }
//     }
//     return nums.sort((a,b)=>{return a-b})
// };
// let nums = [5, 2, 5, 3, 8, 9, 3];
// let R = 4;
// let num = Math.min.apply(null, nums.slice(0, R));
// let T = nums.indexOf(num)
// console.log(nums[T]);
// var nextPermutation = function(nums) {
//     let L=nums.length-2;
//     let R=nums.length-1;
//     while(L>=0){
//         if(nums[R]>nums[L]){
//             let num = Math.min.apply(null, nums.slice(0, R));
//             let T= nums.indexOf(num);
//             [nums[R], nums[T]]=[nums[T],nums[R]];
//              L=nums.length-2;
//             R=nums.length-1;
//             return  nums;
//         }
//         else{
//             L--;
//             R--;
//         }
//     }
//     return nums.sort((a,b)=>{return a-b})
// };